package com.zhugang.week13.prefixsuffixstatistics;

/**
 * @program algorithms
 * @description: maxProfit
 * @author: chanzhugang
 * @create: 2022/09/23 18:27
 */
public class MaxProfit {

    /**
     * 121 买卖股票的最佳时机
     * https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/
     *
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {
        // 求最大值，后缀统计max[], max(max[i] - prices[i])
        int n = prices.length;
        int[] maxArr = new int[n];

        int curMax = 0;
        for (int i = n - 1; i >= 0; i--) {
            // 最大值不包含自己
            maxArr[i] = curMax;
            curMax = Math.max(curMax, prices[i]);
        }

        int result = 0;
        for (int i = 0; i < n; i++) {
            // 更新最大值
            result = Math.max(result, maxArr[i] - prices[i]);
        }
        return result;
    }


    public int maxProfi2(int[] prices) {
        // 暴力求解：求数组中两数的最大差值，且 j > i
        int n = prices.length;
        int maxPrice = 0;
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                maxPrice = Math.max(maxPrice, prices[j] - prices[i]);

               /* if (prices[j] - prices[i] > maxPrice) {
                    maxPrice = prices[j] - prices[i];
                }*/
            }
        }
        return maxPrice;
    }

    public int maxProfi3(int[] prices) {
        // 类似前缀统计最小
        int minPrice = Integer.MAX_VALUE;
        int maxProfit = 0;
        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < minPrice) {
                // 最小值
                minPrice = prices[i];
            } else if (prices[i] - minPrice > maxProfit) {
                maxProfit = prices[i] - minPrice;
            }
        }
        return maxProfit;
    }


    public static void main(String[] args) {
        MaxProfit maxProfit = new MaxProfit();
        int result = maxProfit.maxProfit(new int[]{7, 1, 5, 3, 6, 4});
        System.out.println(result);

    }
}